//
// Created by Administrator on 2023/11/23.
//
#include "bits/stdc++.h"

using namespace std;

const int N = 510, INF = 0x3f3f3f3f;

int g[N][N];
int dist[N];

bool st[N];

int n, m;

int dijkstra() {
    dist[1] = 0;

    for (int i = 0; i < n; ++i) {
        int t = -1;
        //和prim一样 仍维护最小dist值
        for (int j = 1; j <= n; ++j) {
            //t会把j=1覆盖过去
            if (!st[j] && (t == -1 || dist[j] < dist[t])) t = j;
        }

        //更新为已经访问
        st[t] = true;
        //更新dist，注意
        for (int j = 1; j <= n; ++j) {
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        }
    }
    return dist[n];
}


int main() {
    memset(dist, INF, sizeof dist);
    memset(g, INF, sizeof g);
    cin >> n >> m;
    while (m--) {
        int x, y, z;
        cin >> x >> y >> z;
        g[x][y] = z;
    }
    int res= dijkstra();
    if(res!=INF) cout<<res;
    else cout<<"-1";
}